package code.class2;

/**
 * https://leetcode.cn/problems/search-insert-position/description/?envType=problem-list-v2&envId=array
 * 搜索插入位置
 */
public class Code06_searchInsert {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3};
        int target = 3;
        int i = searchInsert(nums, target);
        System.out.println("i = " + i);
    }

    public static int searchInsert(int[] arr, int target) {
        return process(0, arr.length - 1, arr, target);
    }

    public static int process(int l, int r, int[] arr, int target) {
        int ans = arr.length;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (target > arr[mid]) {
                l = mid + 1;
            } else {
                // 当 target <= nums[mid] 时，我们知道目标值 target 应该插入 mid 或者它的前面
                // 1.如果 target == nums[mid]，那么目标值已经存在，返回当前的 mid 就可以了。
                // 2.如果 target < nums[mid]，说明目标值应该插入在 mid 的前面，因为 target 小于当前的中间元素。
                ans = mid; // // 目标值可能插入在 mid 或者其前面
                r = mid - 1; // 搜索左半部分，继续查找最左边的插入位置
            }
        }
        return ans;
    }
}
